1. Field of the Invention
The present invention relates generally to cache memory systems and, more particularly, to managing multi-way associative caches.
2. Related Art
Most computer systems include, among other components, a processor and a memory device. The speed at which the processor can execute instructions and process data depends on the rate at which the instructions and data can be transferred from memory to the processor. In an attempt to reduce the time required for the processor to obtain instructions and data, computer architectures commonly include a memory hierarchy, with smaller, faster memory devices located more proximate to the processor than larger, slower memory devices. Typically, memory hierarchies include a cache memory physically and logically located between the processor and a larger main memory device.
A cache memory is a small, high-speed buffer memory which is used to temporarily hold the contents of main memory which are likely be used in the near future by the processor. Because cache memory typically has access times which are several times faster than those of main memory, the use of cache memory can significantly improve system performance by reducing the time a processor waits for instructions and data to be fetched from and/or stored to memory.
A cache memory comprises many lines of data, commonly referred to as cache entries, which have been copied from the computer system's main memory. Associated with each cache entry is a cache tag. A cache entry's tag provides information for mapping the cache entry's data to its main memory address. Each time a processor requests an instruction or data from memory, a tag comparison is made to determine whether a copy of the requested data resides in the cache. If the desired data is not in the cache, the requested data is retrieved from the main memory, stored in the cache, and supplied to the processor. Commonly used mapping functions for cache data storage include direct mapping and associative mapping techniques.
In a multi-way associative cache, a single index is used to simultaneously access a plurality of cache entries. The collection of all cache entries addressed by a single cache index is referred to as a cache set. The number of cache entries addressed by a single cache index indicates the “way” number of a cache. For example, if in a cache a single cache index is used to access data from two data arrays, the cache is a 2-way associative cache. Similarly, if in a cache a single cache index is used to access data from four data arrays, the cache is a 4-way associative cache.
A multi-way cache access includes performing a tag comparison for each way. If a tag comparison indicates that the desired line of data resides in a particular way, the data line is output from the cache for subsequent use by the processor which requested the data. If the requested data is not stored in the cache, then the data is retrieved from main memory and stored in a way of the cache. Since there are a finite number of data lines in a cache, it is frequently necessary to replace the data stored in a cache as new data is needed. However, each time a new line of data is retrieved from main memory, a determination must be made as to which line of data in the cache is to be replaced. For a multi-way associative cache, this determination involves selecting the way in which the new line of data will be stored.